N = int(input())
for _ in range(N):
n, m, k = map(int, input().split())
h = list(map(int, input().split()))
d = [list(map(int, input().split())) for _ in range(m)]
dep = {}
for i in d:
if i[1] - 1 not in dep:
dep[i[1] - 1] = []
dep[i[1] - 1].append(i[0] - 1)
es = [0] * n ee = [0] * n nd = [0] * n
for i in range(n):
if i in dep:
mes = 0 mnd = -1 for dd in dep[i]:
nnd = nd[dd] + int(h[dd] > h[i])
if nnd > mnd:
mnd = nnd
mes = es[dd]
elif nnd == mnd:
mes = min(mes, es[dd])
es[i] = mes
ee[i] = h[i]
nd[i] = mnd
else:
es[i] = h[i]
ee[i] = h[i]
nd[i] = 0
tee = [k * nd[i] + ee[i] for i in range(len(ee))]
os = sorted(range(len(es)), key=es.__getitem__)
oe = sorted(range(len(tee)), key=tee.__getitem__)
time = max(tee) - min(es)
seen = set()
pmee = max(tee)
nnes = min(es)
nnis = 0
for i in range(len(es) - 1):
seen.add(oe[i])
while os[nnis] in seen:
nnis += 1
nnes = es[os[nnis]]
time = min(time, max(pmee, k + tee[oe[i]]) - nnes)
print(time)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
typedef vector<ll> vll;
#define pb push_back
#define fori(n) for (ll i=0; i<n; i++)
#define forj(n) for (ll j=0; j<n; j++)
#define fork(n) for (ll k=0; k<n; k++)
#define forn(n) for (ll i=1; i<=n; i++)
#define forn2(n) for (ll j=1; j<=n; j++)
#define forn3(n) for (ll k=1; k<=n; k++)
#define Sort(a) sort(a.begin(),a.end())
const int N=2e5+5;
vll g[N];
vll p;
ll k;
vll vis(N),a(N),vis2(N);
vll ans(N);
void dfs(ll v){
vis[v]=true;
for(auto c:g[v]){
if(vis[c]){
// if(minn[c])
continue;
}
dfs(c);
}
p.pb(v);
}
ll mini=1e14,maxi=0;
void dfs2(ll v){
vis2[v]=true;
for(auto c:g[v]){
if(vis2[c]){
if(a[c]<a[v])
{
ans[v]=max(ans[v],ans[c]+k);
}
else ans[v]=max(ans[v],ans[c]);
continue;
}
dfs2(c);
if(a[c]<a[v])
{
ans[v]=max(ans[v],ans[c]+k);
}
else ans[v]=max(ans[v],ans[c]);
}
// maxi=max(maxi,ans[v]);
}
void solve(){
ll n,m;
cin>>n>>m>>k;
vll b;
mini=1e14;maxi=0;
forn(n)
{
cin>>a[i];
b.pb(a[i]);
ans[i]=a[i];
}
fori(m)
{
ll x,y;
cin>>x>>y;
g[x].pb(y);
}
forn(n)
{
if(!vis[i])dfs(i);
}
reverse(p.begin(),p.end());
vector<pair<ll, ll>> ve;
// fori(p.size())
// {
// if(!vis2[p[i]]){
// dfs2(p[i]);
// mini=a[p[i]];
// maxi=ans[p[i]];
// ve.pb({mini,maxi});
// }
// }
forn(n)
{
if(!vis2[i]){
dfs2(i);
mini=a[i];
maxi=ans[i];
ve.pb({mini,maxi});
}
}
// Sort(b);
Sort(ve);
priority_queue<ll> pq;
multiset<ll> st;
fori(ve.size())st.insert(ve[i].second);
ll ves=ve.size();
fori(ves)
{
ve.pb({ve[i].first+k,ve[i].second+k});
}
ll anss=1e14;
fori(ves)
{
auto po=*(--st.end());
anss=min(anss,po-ve[i].first);
st.erase(st.find(ve[i].second));
st.insert(ve[i].second+k);
}
cout<<anss<<endl;
fori(n+3)
{
ans[i]=0;
g[i].clear();
vis[i]=0;
vis2[i]=0;
}
p.clear();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//Redeem yourself King.
ll n;
cin>>n;
while(n--)solve();
return 0;
}
20. Valid Parentheses | 746. Min Cost Climbing Stairs |
392. Is Subsequence | 70. Climbing Stairs |
53. Maximum Subarray | 1527A. And Then There Were K |
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers | 318. Maximum Product of Word Lengths |
448. Find All Numbers Disappeared in an Array | 1155. Number of Dice Rolls With Target Sum |
415. Add Strings | 22. Generate Parentheses |
13. Roman to Integer | 2. Add Two Numbers |
515. Find Largest Value in Each Tree Row | 345. Reverse Vowels of a String |
628. Maximum Product of Three Numbers | 1526A - Mean Inequality |
1526B - I Hate 1111 | 1881. Maximum Value after Insertion |
237. Delete Node in a Linked List | 27. Remove Element |
39. Combination Sum | 378. Kth Smallest Element in a Sorted Matrix |
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |
1051. Height Checker | 695. Max Area of Island |